package com.yubest;

import java.util.*;

/**
 * 给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。
 *
 * 整数除法仅保留整数部分。
 *
 *  
 *
 * 示例 1：
 *
 * 输入：s = "3+2*2"
 * 输出：7
 * 示例 2：
 *
 * 输入：s = " 3/2 "
 * 输出：1
 * 示例 3：
 *
 * 输入：s = " 3+5 / 2 "
 * 输出：5
 *  
 *
 * 提示：
 *
 * 1 <= s.length <= 3 * 10^5
 * s 由整数和算符 ('+', '-', '*', '/') 组成，中间由一些空格隔开
 * s 表示一个 有效表达式
 * 表达式中的所有整数都是非负整数，且在范围 [0, 2^31 - 1] 内
 * 题目数据保证答案是一个 32-bit 整数
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/basic-calculator-ii
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * @Author hweiyu
 * @Description
 * @Date 2022/1/18 10:48
 */
public class P0227 {
}

class Solution227 {

    public int calculate(String s) {
        List<String> list = new ArrayList<>();
        StringBuilder buf = new StringBuilder();
        for (int i = 0; i < s.length(); i++) {
            if (' ' == s.charAt(i)) {
                continue;
            }
            if (isNumber(s.charAt(i))) {
                buf.append(s.charAt(i));
            } else {
                if (buf.length() > 0) {
                    list.add(buf.toString());
                    buf.setLength(0);
                }
                list.add(String.valueOf(s.charAt(i)));
            }
        }
        if (buf.length() > 0) {
            list.add(buf.toString());
        }
        //转逆波兰表达式
        String[] expression = infillToSuffix(list.toArray(new String[]{}));
        //逆波兰求解
        return evalRPN(expression);
    }

    private boolean isNumber(char c) {
        return c >= '0' && c <= '9';
    }

    /**
     * 中缀转后缀
     *
     * @param arr
     * @return
     */
    private String[] infillToSuffix(String[] arr) {
        /**
         * 定义操作符的优先级
         * ( ) > * / > + -
         * key: 操作符，value: 优先级
         */
        Map<String, Integer> priorityMap = new HashMap<>();
        priorityMap.put("(", 2);
        priorityMap.put(")", 2);
        priorityMap.put("*", 1);
        priorityMap.put("/", 1);
        priorityMap.put("+", 0);
        priorityMap.put("-", 0);

        List<String> result = new ArrayList<>();
        Stack<String> opStack = new Stack<>();
        for (String str : arr) {
            //如果是操作符
            if (priorityMap.containsKey(str)) {
                //弹出优先级大于等于当前操作符的操作符，并将当前操作符入栈
                pop(str, opStack, priorityMap, result);
            } else {
                result.add(str);
            }
        }

        //栈出所有操作符全部弹出
        while (!opStack.isEmpty()) {
            result.add(opStack.pop());
        }
        return result.toArray(new String[]{});
    }

    /**
     * 操作符出栈
     * <p>
     * 规则：
     * 1、当前操作符是右括号时，弹出所有操作符，直到遇到左括号；并且左括号也弹出，但不加入结果集
     * 2、弹出优先级大于等于当前操作符的操作符
     *
     * @param curOp  当前操作符
     * @param result 结果集
     */
    private void pop(String curOp, Stack<String> opStack, Map<String, Integer> priorityMap, List<String> result) {
        String cur;
        //遇到右括号时，弹出所有操作符，直到遇到左括号
        if (")".equals(curOp)) {
            while (!opStack.isEmpty()) {
                cur = opStack.pop();
                if ("(".equals(cur)) {
                    //左括号仅弹出，不放入结果集，因为逆波兰表达式不需要括号
                    break;
                }
                result.add(cur);
            }
        } else {
            //当前操作符的优先级
            int curPriority = priorityMap.get(curOp);
            /**
             * 1、弹出优先级大于等于当前操作符的操作符
             * 2、栈为空或遇到左括号，则结束遍历
             */
            while (!opStack.isEmpty()
                    && curPriority <= priorityMap.get(opStack.peek())
                    && !"(".equals(opStack.peek())) {
                result.add(opStack.pop());
            }
        }
        //当前操作符进栈
        if (!")".equals(curOp)) {
            opStack.push(curOp);
        }
    }

    private int evalRPN(String[] tokens) {
        Stack<Integer> nums = new Stack<>();
        Integer a, b, c = null;
        for (String token : tokens) {
            if (isOp(token)) {
                b = nums.pop();
                a = nums.pop();
                if ("+".equals(token)) {
                    c = a + b;
                } else if ("-".equals(token)) {
                    c = a - b;
                } else if ("*".equals(token)) {
                    c = a * b;
                } else if ("/".equals(token)) {
                    c = a / b;
                }
                nums.push(c);
            } else {
                nums.push(Integer.valueOf(token));
            }
        }
        return nums.pop();
    }

    private boolean isOp(String str) {
        return "+".equals(str) || "-".equals(str) || "*".equals(str) || "/".equals(str);
    }
}
